// Compiler for PHP (aka KPHP)
// Copyright (c) 2020 LLC «V Kontakte»
// Distributed under the GPL v3 License, see LICENSE.notice.txt

#pragma once

#include "runtime-common/core/core-types/decl/array_iterator.h"
#include "runtime-common/core/include.h"

#ifndef INCLUDED_FROM_KPHP_CORE
#error "this file must be included only from runtime-core.h"
#endif

struct array_size {
  int64_t size{0};
  bool is_vector{false};

  array_size() = default;

  inline array_size(int64_t int_size, bool is_vector) noexcept;

  inline array_size operator+(const array_size& other) const noexcept;

  inline array_size& cut(int64_t length) noexcept;

  inline array_size& min(const array_size& other) noexcept;
};

namespace dl {
template<class T, class TT, class T1>
void sort(TT* begin_init, TT* end_init, T1 compare) noexcept;
}

namespace array_functions_impl_ {
/*
 * async analog of array::sort and array::ksort since in runtime-light comparator can be coroutine
 * */
template<typename Result, typename U, typename Comparator>
Result async_sort(array<U>& arr, Comparator comparator, bool renumber) noexcept;

template<typename Result, typename U, typename Comparator>
Result async_ksort(array<U>& arr, Comparator comparator) noexcept;
} // namespace array_functions_impl_

enum class overwrite_element { YES, NO };

enum class merge_recursive { YES, NO };

using list_entry_pointer_type = uint32_t;

struct array_list_hash_entry {
  list_entry_pointer_type next;
  list_entry_pointer_type prev;
};

struct ArrayBucketDummyStrTag {};

struct array_inner_control {
  bool is_vector_internal;
  int ref_cnt;
  int64_t max_key;
  array_list_hash_entry last;
  uint32_t size;
  uint32_t buf_size;
};

template<class T>
class array {
public:
  // TODO why we need 2 value types?
  using ValueType = T;
  using value_type = T;
  using key_type = mixed;

  inline static bool is_int_key(const key_type& key);

private:
  using entry_pointer_type = list_entry_pointer_type;
  using list_hash_entry = array_list_hash_entry;

  // array_bucket struct represent array bucket
  // if key is number, int_key contains this number, there is no string_key.
  // if key is string, int_key contains hash of this string, string_key contains this string.
  struct array_bucket : list_hash_entry {
    T value;

    int64_t int_key;
    string string_key;

    inline key_type get_key() const;
  };

  struct array_inner_fields_for_map {
    // this helper value is claimed to improve performance by avoiding % division
    uint64_t modulo_helper_buf_size{0};
    // track number of string keys in map
    // it is useful in some specific cases, see has_no_string_keys()
    uint32_t string_size{0};
  };

  struct alignas(array_bucket) array_inner : array_inner_control {
    static constexpr uint32_t MAX_HASHTABLE_SIZE = (1 << 26);
    // empty hash_entry identified by (next == EMPTY_POINTER)
    static constexpr entry_pointer_type EMPTY_POINTER = 0;
    static constexpr size_t ENTRIES_OFFSET = sizeof(array_inner);

    inline bool is_vector() const noexcept __attribute__((always_inline));

    inline array_bucket* entries() noexcept __attribute__((always_inline));
    inline const array_bucket* entries() const noexcept __attribute__((always_inline));

    inline list_hash_entry* get_entry(entry_pointer_type pointer) const __attribute__((always_inline));
    inline entry_pointer_type get_pointer(list_hash_entry* entry) const __attribute__((always_inline));

    inline const array_bucket* begin() const __attribute__((always_inline)) ubsan_supp("alignment");
    inline const array_bucket* next(const array_bucket* ptr) const __attribute__((always_inline)) ubsan_supp("alignment");
    inline const array_bucket* prev(const array_bucket* ptr) const __attribute__((always_inline)) ubsan_supp("alignment");
    inline const array_bucket* end() const __attribute__((always_inline)) ubsan_supp("alignment");
    inline array_bucket* begin() __attribute__((always_inline)) ubsan_supp("alignment");
    inline array_bucket* next(array_bucket* ptr) __attribute__((always_inline)) ubsan_supp("alignment");
    inline array_bucket* prev(array_bucket* ptr) __attribute__((always_inline)) ubsan_supp("alignment");
    inline array_bucket* end() __attribute__((always_inline)) ubsan_supp("alignment");

    inline bool is_string_hash_entry(const array_bucket* ptr) const __attribute__((always_inline));

    inline array_inner_fields_for_map& fields_for_map() __attribute__((always_inline));
    inline const array_inner_fields_for_map& fields_for_map() const __attribute__((always_inline));

    inline uint32_t choose_bucket(int64_t key) const noexcept __attribute__((always_inline));
    inline uint32_t choose_bucket(const array_inner_fields_for_map& fields, int64_t key) const noexcept __attribute__((always_inline));

    inline static size_t sizeof_vector(uint32_t int_size) noexcept __attribute__((always_inline));
    inline static size_t sizeof_map(uint32_t int_size) noexcept __attribute__((always_inline));
    inline static size_t estimate_size(int64_t& new_int_size, bool is_vector);
    inline static array_inner* create(int64_t new_int_size, bool is_vector);

    inline static array_inner* empty_array() __attribute__((always_inline));

    inline void dispose();

    inline array_inner* ref_copy() __attribute__((always_inline));

    template<class... Args>
    inline T& emplace_back_vector_value(Args&&... args) noexcept;
    inline T& push_back_vector_value(const T& v); // unsafe

    template<class... Args>
    inline T& emplace_vector_value(int64_t int_key, Args&&... args) noexcept;
    inline T& set_vector_value(int64_t int_key, const T& v); // unsafe

    template<class... Args>
    inline T& emplace_int_key_map_value(overwrite_element policy, int64_t int_key, Args&&... args) noexcept;
    inline T& set_map_value(overwrite_element policy, int64_t int_key, const T& v);

    template<class STRING, class... Args>
    inline std::pair<T&, bool> emplace_string_key_map_value(overwrite_element policy, int64_t int_key, STRING&& string_key, Args&&... args) noexcept;
    inline T& set_map_value(overwrite_element policy, int64_t int_key, const string& string_key, const T& v);

    inline T unset_vector_value();
    inline T unset_map_value(int64_t int_key);

    // to avoid the const_cast, declare these functions as static with a template self parameter (this)
    template<class S>
    static auto& find_map_entry(S& self, int64_t int_key) noexcept;
    template<class S>
    static auto& find_map_entry(S& self, const string& string_key, int64_t precomputed_hash) noexcept;
    template<class S>
    static auto& find_map_entry(S& self, const char* key, string::size_type key_size, int64_t precomputed_hash) noexcept;

    template<class... Key>
    inline const T* find_map_value(Key&&... key) const noexcept;
    inline const T* find_vector_value(int64_t int_key) const noexcept;
    inline T* find_vector_value(int64_t int_key) noexcept;

    inline const T& get_vector_value(int64_t int_key) const; // unsafe
    inline T& get_vector_value(int64_t int_key);             // unsafe
    inline T unset_map_value(const string& string_key, int64_t precomputed_hash);

    bool is_vector_internal_or_last_index(int64_t key) const noexcept;
    bool has_no_string_keys() const noexcept;

    size_t estimate_memory_usage() const noexcept;
    size_t calculate_memory_for_copying() const noexcept;

    inline array_inner(const array_inner& other) = delete;
    inline array_inner& operator=(const array_inner& other) = delete;
  };

  inline bool mutate_if_vector_shared(uint32_t mul = 1);
  inline bool mutate_to_size_if_vector_shared(int64_t int_size);
  inline void mutate_to_size(int64_t int_size);
  inline bool mutate_if_map_shared(uint32_t mul = 1);
  inline void mutate_if_vector_needs_space();
  inline void mutate_if_map_needs_space();
  inline void mutate_to_map_if_vector_or_map_need_space();

  inline void convert_to_map();

  template<class T1>
  inline void copy_from(const array<T1>& other);

  template<class T1>
  inline void move_from(array<T1>&& other) noexcept;

  inline void destroy();

public:
  friend class array_iterator<T>;
  friend class array_iterator<const T>;

  using iterator = array_iterator<T>;
  using const_iterator = array_iterator<const T>;

  inline array() __attribute__((always_inline));

  inline explicit array(const array_size& s) __attribute__((always_inline));

  template<class KeyT>
  inline array(const std::initializer_list<std::pair<KeyT, T>>& list) __attribute__((always_inline));

  inline array(const array& other) noexcept __attribute__((always_inline));

  inline array(array&& other) noexcept __attribute__((always_inline));

  template<class T1, class = enable_if_constructible_or_unknown<T, T1>>
  inline array(const array<T1>& other) noexcept __attribute__((always_inline));

  template<class T1, class = enable_if_constructible_or_unknown<T, T1>>
  inline array(array<T1>&& other) noexcept __attribute__((always_inline));

  template<class... Args>
  inline static array create(Args&&... args) __attribute__((always_inline));

  inline array& operator=(const array& other) noexcept __attribute__((always_inline));

  inline array& operator=(array&& other) noexcept __attribute__((always_inline));

  template<class T1, class = enable_if_constructible_or_unknown<T, T1>>
  inline array& operator=(const array<T1>& other) noexcept;

  template<class T1, class = enable_if_constructible_or_unknown<T, T1>>
  inline array& operator=(array<T1>&& other) noexcept;

  inline ~array();

  inline void clear() __attribute__((always_inline));

  // shows if internal storage is vector
  inline bool is_vector() const __attribute__((always_inline));
  // internal storage may be map, but it still behaves exactly like vector
  inline bool is_pseudo_vector() const __attribute__((always_inline));
  // and one more level deep: shows if there are no string keys in storage;
  // it is useful in some specific cases like in shift() function,
  // there we drop all int indexes, and if there will be also no string indexes
  // we can create true vector
  bool has_no_string_keys() const noexcept;

  static size_t estimate_size(int64_t n, bool is_vector) noexcept {
    return array_inner::estimate_size(n, is_vector);
  }

  T& operator[](int64_t int_key);
  T& operator[](int32_t key) {
    return (*this)[int64_t{key}];
  }
  T& operator[](const string& s);
  T& operator[](tmp_string s);
  T& operator[](const mixed& v);
  T& operator[](double double_key);
  T& operator[](const const_iterator& it) noexcept;
  T& operator[](const iterator& it) noexcept;

  template<class... Args>
  void emplace_value(int64_t int_key, Args&&... args) noexcept;
  void set_value(int64_t int_key, T&& v) noexcept;
  void set_value(int64_t int_key, const T& v) noexcept;
  void set_value(int32_t key, T&& v) noexcept {
    set_value(int64_t{key}, std::move(v));
  }
  void set_value(int32_t key, const T& v) noexcept {
    set_value(int64_t{key}, v);
  }
  void set_value(double double_key, T&& v) noexcept;
  void set_value(double double_key, const T& v) noexcept;

  template<class... Args>
  void emplace_value(const string& string_key, Args&&... args) noexcept;
  void set_value(const string& string_key, T&& v) noexcept;
  void set_value(const string& string_key, const T& v) noexcept;
  void set_value(tmp_string string_key, T&& v) noexcept;
  void set_value(tmp_string string_key, const T& v) noexcept;

  void set_value(const string& string_key, T&& v, int64_t precomputed_hash) noexcept;
  void set_value(const string& string_key, const T& v, int64_t precomputed_hash) noexcept;

  template<class... Args>
  void emplace_value(const mixed& var_key, Args&&... args) noexcept;
  void set_value(const mixed& v, T&& value) noexcept;
  void set_value(const mixed& v, const T& value) noexcept;

  template<class OptionalT, class... Args>
  void emplace_value(const Optional<OptionalT>& key, Args&&... args) noexcept;
  template<class OptionalT>
  void set_value(const Optional<OptionalT>& key, T&& value) noexcept;
  template<class OptionalT>
  void set_value(const Optional<OptionalT>& key, const T& value) noexcept;

  void set_value(const const_iterator& it) noexcept;
  void set_value(const iterator& it) noexcept;

  // assign binary array_inner representation
  // can be used only on empty arrays to receive logically const array
  void assign_raw(const char* s);

  const T* find_value(int64_t int_key) const noexcept;
  const T* find_value(int32_t key) const noexcept {
    return find_value(int64_t{key});
  }
  const T* find_value(const char* s, string::size_type l) const noexcept;
  const T* find_value(tmp_string s) const noexcept {
    return find_value(s.data, s.size);
  }
  const T* find_value(const string& s) const noexcept {
    return find_value(s.c_str(), s.size());
  }
  const T* find_value(const string& s, int64_t precomputed_hash) const noexcept;
  const T* find_value(const mixed& v) const noexcept;
  const T* find_value(double double_key) const noexcept;
  const T* find_value(const const_iterator& it) const noexcept;
  const T* find_value(const iterator& it) const noexcept;

  // All non-const methods find_no_mutate() do not lead to a copy
  iterator find_no_mutate(int64_t int_key) noexcept;
  iterator find_no_mutate(const string& string_key) noexcept;
  iterator find_no_mutate(const mixed& v) noexcept;

  template<class K>
  const mixed get_var(const K& key) const;

  template<class K>
  const T get_value(const K& key) const;
  const T get_value(const string& string_key, int64_t precomputed_hash) const;

  template<class... Args>
  T& emplace_back(Args&&... args) noexcept;
  void push_back(T&& v) noexcept;
  void push_back(const T& v) noexcept;

  void push_back(const const_iterator& it) noexcept;
  void push_back(const iterator& it) noexcept;

  const T push_back_return(const T& v);
  const T push_back_return(T&& v);

  void swap_int_keys(int64_t idx1, int64_t idx2) noexcept;

  inline void fill_vector(int64_t num, const T& value);
  inline void memcpy_vector(int64_t num, const void* src_buf);

  inline int64_t get_next_key() const __attribute__((always_inline));

  template<class K>
  bool has_key(const K& key) const;

  template<class K>
  bool isset(const K& key) const noexcept;
  bool isset(const string& key, int64_t precomputed_hash) const noexcept;

  T unset(int64_t int_key);
  T unset(int32_t key) {
    return unset(int64_t{key});
  }
  T unset(double double_key) {
    return unset(static_cast<int64_t>(double_key));
  }
  T unset(const string& string_key);
  T unset(const string& string_key, int64_t precomputed_hash);
  T unset(const mixed& var_key);

  inline bool empty() const __attribute__((always_inline));
  inline int64_t count() const __attribute__((always_inline));

  inline array_size size() const __attribute__((always_inline));

  template<class T1, class = enable_if_constructible_or_unknown<T, T1>>
  void merge_with(const array<T1>& other) noexcept;
  template<class T1, class = enable_if_constructible_or_unknown<T, T1>>
  void merge_with_recursive(const array<T1>& other) noexcept;
  void merge_with_recursive(const mixed& other) noexcept;

  const array operator+(const array& other) const;
  array& operator+=(const array& other);

  inline const_iterator begin() const __attribute__((always_inline));
  inline const_iterator cbegin() const __attribute__((always_inline));
  inline const_iterator middle(int64_t n) const __attribute__((always_inline));
  inline const_iterator end() const __attribute__((always_inline));
  inline const_iterator cend() const __attribute__((always_inline));

  inline iterator begin() __attribute__((always_inline));
  inline iterator middle(int64_t n) __attribute__((always_inline));
  inline iterator end() __attribute__((always_inline));

  template<class T1>
  void sort(const T1& compare, bool renumber);

  template<class T1>
  void ksort(const T1& compare);

  inline void swap(array& other) __attribute__((always_inline));

  T pop();
  T& back();

  T shift();

  int64_t unshift(const T& val);

  inline bool to_bool() const __attribute__((always_inline));
  inline int64_t to_int() const __attribute__((always_inline));
  inline double to_float() const __attribute__((always_inline));

  int64_t get_reference_counter() const;
  bool is_reference_counter(ExtraRefCnt ref_cnt_value) const noexcept;
  void set_reference_counter_to(ExtraRefCnt ref_cnt_value) noexcept;
  void force_destroy(ExtraRefCnt expected_ref_cnt) noexcept;

  iterator begin_no_mutate();
  iterator end_no_mutate();

  void mutate_if_shared() noexcept;

  const T* get_const_vector_pointer() const; // unsafe
  T* get_vector_pointer();                   // unsafe

  bool is_equal_inner_pointer(const array& other) const noexcept;

  void reserve(int64_t int_size, bool make_vector_if_possible);

  size_t estimate_memory_usage() const noexcept;
  size_t calculate_memory_for_copying() const noexcept;

  template<typename U>
  static array<T> convert_from(const array<U>&);

private:
  template<class... Key>
  iterator find_iterator_in_map_no_mutate(const Key&... key) noexcept;

  template<merge_recursive recursive>
  std::enable_if_t<recursive == merge_recursive::YES> start_merge_recursive(T& value, bool was_inserted, const T& other_value) noexcept;
  template<merge_recursive recursive>
  std::enable_if_t<recursive == merge_recursive::NO> start_merge_recursive(T& /*value*/, bool /*was_inserted*/, const T& /*other_value*/) noexcept {}

  template<merge_recursive recursive = merge_recursive::NO, class T1>
  void push_back_iterator(const array_iterator<T1>& it) noexcept;

  array_inner* p;

  template<class T1>
  friend class array;

  template<typename Result, typename U, typename Comparator>
  friend Result array_functions_impl_::async_sort(array<U>& arr, Comparator comparator, bool renumber) noexcept;

  template<typename Result, typename U, typename Comparator>
  friend Result array_functions_impl_::async_ksort(array<U>& arr, Comparator comparator) noexcept;
};

template<class T>
inline void swap(array<T>& lhs, array<T>& rhs);

template<class T>
inline const array<T> array_add(array<T> a1, const array<T>& a2);
